:- module(graph_algorithms). :- export incremental_single_pair_all_shortest_paths_as_graph / 7. :- export incremental_single_pair_shortest_path / 6. :- export incremental_all_shortest_paths_as_graph / 6. :- export incremental_all_shortest_paths_as_edges / 6. :- export maximum_matching_hopcroft_karp / 4. :- export minimum_spanning_forest / 5. :- export minimum_spanning_tree / 4. :- export single_pair_all_shortest_paths / 5. :- export all_shortest_paths / 4. :- export shortest_paths_bellman_ford / 4. :- export single_pair_shortest_path_bellman_ford / 5. :- export possible_path / 6. :- export single_pair_all_short_paths_as_graph / 7. :- export possible_path / 7. :- export single_pair_short_path / 6. :- export all_short_paths_as_graph / 6. :- export all_short_paths_as_edges / 6. :- export single_pair_shortest_path / 5. :- export shortest_paths / 4. :- export strong_components / 2. :- export biconnected_components / 3. :- export articulation_points / 2. :- export critical_links / 2. :- export connected_components / 2. :- export graph_cycles / 2. :- export graph_is_acyclic / 1. :- export top_sort / 2. :- export is_sub_graph / 2. :- export graph_is_bidirected / 1. :- export proper_graph / 1. :- export graph_edge / 2. :- export graph_adjacent_edge / 3. :- export graph_node / 2. :- export graph_get_edges / 4. :- export graph_get_edge / 4. :- export nodenames_to_nodes / 3. :- export nodes_to_nodenames / 3. :- export node_to_nodename / 3. :- export graph_get_nodenames / 2. :- export graph_get_incoming_edges / 3. :- export graph_get_adjacent_edges / 3. :- export graph_reverse_edges / 2. :- export graph_set_random_weights / 3. :- export make_random_graph / 6. :- export graph_get_maxnode / 2. :- export graph_get_all_edges / 2. :- export make_undirected_graph / 2. :- export graph_set_nodenames / 2. :- export nodename_to_node / 3. :- export make_graph_symbolic / 3. :- export make_sub_graph / 3. :- export make_graph / 3. :- comment(summary, "Collection of graph algorithms"). :- comment(author, "Joachim Schimpf"). :- comment(date, "$Date: 2004/12/09 16:12:33 $"). :- comment(copyright, "Imperial College London and Parc Technologies"). :- comment(desc, html("

\n This library is a collection of graph algorithms.\n

\n In its simplest form, a graph consists of a (possibly empty) set of\n nodes (numbered from 1 to NNodes), and zero or more directed edges\n between these nodes. An edge is represented by the data structure\n

\n\te(Source, Target, EdgeData)\n
\n where Source and Target are integers indicating the start and end\n point of the edge, and EdgeData is an arbitrary data structure\n holding additional information about the edge, e.g. capacity,\n distance, weight, name etc. The EdgeData field should have the\n same structure for all edges in a graph. If there is no\n information attached to edges, the field should be set to 1\n for edges between different nodes and to 0 otherwise.\n Several library predicates inspect the EdgeData field or an argument\n of the EdgeData field, e.g. the shortest path predicate can\n use any numeric component of EdgeData as the distance criterion.\n

\n The most efficient way to create a graph is to use make_graph/3\n which takes the number of nodes and a list of edges and constructs\n the graph data structure. For example, the 13-node graph from\n Sedgewick, figure 32.1 can be created as follows:\n

\n    make_graph( 13,\n\t[ e(1,6,1),e(1,2,1),e(1,7,1),e(3,1,1),e(4,6,1),e(5,4,1),\n\t  e(6,5,1),e(7,5,1),e(7,10,1),e(7,3,1),e(8,7,1),e(8,9,1),e(9,8,1),\n\t  e(10,11,1),e(10,12,1),e(10,13,1),e(12,7,1),e(12,13,1),e(13,12,1) ],\n        Graph).\n
\n Often, the nodes have names or other information attached.\n This can be added to the Graph using graph_set_nodenames/2 which\n takes an existing graph and adds an array of node information\n (usually the node names, but any ground term can be used).\n For the Sedgewick-graph above, we could invoke\n
\n    graph_set_nodenames(Graph, [](a,b,c,d,e,f,g,h,i,j,k,l,m))\n
\n If nodes have names anyway, it can be more convenient to specify\n the edges in terms of these node names rather than node numbers.\n Such symbolic edges are written in the form\n
\n\tedge(SourceName, TargetName, EdgeData)\n
\n where SourceName and TargetName should match an entry (usually the\n node name) in the graph's nodename-array. A graph can now be\n constructed by giving a nodename-array and a list of symbolic edges\n to make_graph_symbolic/3, e.g. to build the same graph as above, use\n
\n    make_graph_symbolic(\n\t[](a,b,c,d,e,f,g,h,i,j,k,l,m),\n\t[ edge(a,f,1),edge(a,b,1),edge(a,g,1),edge(c,a,1),edge(d,f,1),edge(e,d,1),\n\t  edge(f,e,1),edge(g,e,1),edge(g,j,1),edge(g,c,1),edge(h,g,1),edge(h,i,1),edge(i,h,1),\n\t  edge(j,k,1),edge(j,l,1),edge(j,m,1),edge(l,g,1),edge(l,m,1),edge(m,l,1) ],\n\tGraph).\n
\n Note the use of the functor e/3 for the internal edge representation\n and edge/3 for the symbolic edge representation.\n

\n There is no special data structure for undirected graphs - they can\n be represented by having reverse edges corresponding to every edge.\n It is allowed to have parallel edges (more than one edge from S to T)\n as long as their EdgeData fields differ.\n

Visualization

\n You can use library(graphviz) or lib(viewable) to draw these graphs.\n

Overview of Shortest-Path Functionality

\n This library provides a number of different variants of shortest path\n algorithms, of which the following table gives an overview:\n\n\n\n \n \n \n \n \n\n\n\n \n \n \n \n \n\n\n\n \n \n \n \n \n\n\n\n \n \n \n \n \n\n\n\n \n \n \n \n \n\n\n\n \n \n \n \n \n\n\n\n \n \n \n \n \n\n\n\n \n \n \n \n \n\n\n\n \n \n \n \n \n\n\n\n \n \n \n \n \n\n\n\n \n \n \n \n \n\n\n\n \n \n \n \n \n\n\n\n \n \n \n \n \n\n
PredicateSinksPathsDeterminismEdge WeightsTolerance
shortest_paths/4allonedetnon-negativeno
shortest_paths_bellman_ford/4allonedetarbitraryno
all_short_paths_as_graph/6allalldetnon-negativeyes
all_short_paths_as_edges/6 + possible_path/7allallnondetnon-negativeyes
incremental_all_shortest_paths_as_graph/6allalldetpositiveno
incremental_all_shortest_paths_as_edges/6 + possible_path/7allallnondetpositiveno
single_pair_shortest_path/5singleonesemidetnon-negativeno
single_pair_shortest_path_bellman_ford/5singleonesemidetarbitraryno
single_pair_all_short_paths_as_graph/7singlealldetnon-negativeyes
single_pair_short_path/6singleallnondetnon-negativeyes
incremental_single_pair_all_shortest_paths_as_graph/7singlealldetpositiveno
incremental_single_pair_shortest_path/6singleallnondetpositiveno
\n\n

To-do list

\n The following operations should be added:\n\n

")). :- comment(all_short_paths_as_edges / 6, [summary : "Computes all shortest paths from a single source to every reachable node", amode : all_short_paths_as_edges(+, +, +, +, -, -), args : ["Graph" : "a graph structure", "DistanceArg" : "which argument of EdgeData to use as distance (integer)", "SourceNode" : "source node number (integer)", "Tolerance" : "tolerable deviation from minimal length (non-negative number)", "Lengths" : "array of numbers (minimum path lengths)", "Predecessors" : "array of lists of e/3 edge structures"], see_also : [possible_path / 7, shortest_paths / 4, single_pair_shortest_path / 5, all_short_paths_as_graph / 6, single_pair_short_path / 6, single_pair_all_short_paths_as_graph / 7], eg : "\n ?- sample_graph(G), all_short_paths_as_edges(G, 0, 1, 0, L, E).\n L = [](0, 1, 2, 3, 2, 1, 1, _326, _327, 2, 3, 3, 3)\n E = []([], [e(1, 2, 1)], [e(7, 3, 1)], [e(5, 4, 1)],\n\t [e(7, 5, 1), e(6, 5, 1)], [e(1, 6, 1)], [e(1, 7, 1)],\n\t _342, _343, [e(7, 10, 1)], [e(10, 11, 1)], [e(10, 12, 1)],\n\t [e(10, 13, 1)])\n ", desc : html("

\n Computes all shortest paths from the single source node SourceNode\n to every sink node which is reachable from it. The result is returned\n in the form of the Predecessors array which contains all relevant edges.\n

\n DistanceArg refers to the graph's EdgeData information that was\n specified when the graph was constructed. If EdgeData is a simple\n number, then DistanceArg should be 0 and EdgeData will be taken\n as the length of the edge. If EdgeData is a compound data structure,\n DistanceArg should be a number between 1 and the arity of that\n structure and determines which argument of the EdgeData structure\n will be interpreted as the edge's length. Important: the distance\n information in EdgeData must be a non-negative number.\n

\n If DistanceArg is given as -1, then any EdgeData is ignored and\n the length of every edge is assumed to be equal to 1.\n

\n SourceNode is the common starting point for the computed paths.\n

\n Tolerance should be zero in order to find only the shortest paths. \n If Tolerance is greater than zero, then all paths that are within\n this tolerance of the shortest path length will be found.\n

\n The result is returned in the form of two arrays, whose indices range\n over the possible sink nodes. The Lengths array indicates the length\n of a shortest path from SourceNode to the corresponding sink node.\n The Predecessors array is an array of edge lists, each list containing\n the alternative edges that are part of a shortest path from SourceNode\n to the corresponding sink node.\n

\n If there is no path from SourceNode to a sink node J, then both\n Lengths[J] and Predecessors[J] are uninstantiated. Otherwise,\n Lengths[J] contains the length of a shortest path from SourceNode to J.\n Predecessors[J] is contains a list of alternative edges that lead from\n some predecessor node to J in a shortest path from SourceNode to J.\n Predecessors[SourceNode] is always the empty list [].\n

\n

Assembling Actual Paths

\n

\n To generate an actual path from the Predecessors array, start from the\n sink node J, select one of the alternative edges in Predecessors[J]\n to find a predecessor node, and continue this process until the SourceNode\n is reached. Depending on the parameters, the following 3 cases can occur:\n

    \n
  1. Tolerance is zero, and Graph did not contain zero-length edges: in this\n case, SubGraph is cycle-free and shortest paths can be found by simply\n selecting arbitrary incoming edges until SourceNode is reached.\n
  2. Tolerance is zero, and Graph did contain zero-length edges: in this case,\n SubGraph may contain (zero-length) cycles which one may want to exclude\n when constructing paths.\n
  3. Tolerance is nonzero: in this case, SubGraph may contain\n cycles (of maximum length Tolerance). Moreover, it may be\n possible to use the edges in SubGraph to construct cycle-free paths\n whose total length is greater than the shortest path length plus\n the tolerance. These may need to be excluded explicitly.\n
\n The possible_path/7 predicate implements this path construction and\n does the necesssary checks to exclude cycles and overly long paths.\n

")]). :- comment(all_short_paths_as_graph / 6, [summary : "Computes all shortest paths from a single source in form of a subgraph", amode : all_short_paths_as_graph(+, +, +, +, -, -), args : ["Graph" : "a graph structure", "DistanceArg" : "which argument of EdgeData to use as distance (integer)", "SourceNode" : "source node number (integer)", "Tolerance" : "tolerable deviation from minimal length (non-negative number)", "Lengths" : "array of numbers (minimum path lengths)", "SubGraph" : "a graph structure"], see_also : [possible_path / 7, shortest_paths / 4, single_pair_shortest_path / 5, all_short_paths_as_edges / 6, single_pair_short_path / 6, single_pair_all_short_paths_as_graph / 7, graph_get_incoming_edges / 3, graph_set_nodenames / 2], eg : "\n ?- sample_graph(G), all_short_paths_as_graph(G, 0, 1, 0, L, E).\n G = graph(13, []([e(1, 6, 1), e(1, 2, 1), e(1, 7, 1)], [], ...)\n L = [](0, 1, 2, 3, 2, 1, 1, _326, _327, 2, 3, 3, 3)\n SG = graph(13, []([e(1, 7, 1), e(1, 6, 1), e(1, 2, 1)], [], ...)\n Yes (0.00s cpu)\n ", desc : html("

\n Computes all shortest paths from the single source node SourceNode\n to every sink node which is reachable from it. The result is returned\n in the form of a sub-graph of the input graph, which contains all\n relevant edges.\n

\n DistanceArg refers to the graph's EdgeData information that was\n specified when the graph was constructed. If EdgeData is a simple\n number, then DistanceArg should be 0 and EdgeData will be taken\n as the length of the edge. If EdgeData is a compound data structure,\n DistanceArg should be a number between 1 and the arity of that\n structure and determines which argument of the EdgeData structure\n will be interpreted as the edge's length. Important: the distance\n information in EdgeData must be a non-negative number.\n

\n If DistanceArg is given as -1, then any EdgeData is ignored and\n the length of every edge is assumed to be equal to 1.\n

\n SourceNode is the common starting point for the computed paths.\n

\n Tolerance should be zero in order to find only the shortest paths. \n If Tolerance is greater than zero, then all paths that are within\n this tolerance of the shortest path length will be found.\n

\n The result is returned in the form of SubGraph, which is a\n sub-graph of the input Graph, containing the same nodes, but only\n those edges that are needed to construct the shortest paths for\n the given parameters. SubGraph does not inherit the nodename\n information from Graph, this can be set explicitly if required.\n

\n In addition, a Lengths array is returned, whose entries indicate\n the length of a shortest path from SourceNode to the corresponding\n sink node. If there is no path from SourceNode to a sink node J,\n then Lengths[J] is uninstantiated.\n

\n

Properties of the resulting SubGraph

\n

\n To generate an actual path from the resulting SubGraph, start from the\n sink node J, select one of its incoming edges (graph_get_incoming_edges/3)\n to find a predecessor node, and continue this process until the SourceNode\n is reached. Depending on the parameters, the following 3 cases can occur:\n

    \n
  1. Tolerance is zero, and Graph did not contain zero-length edges: in this\n case, SubGraph is cycle-free and shortest paths can be found by simply\n selecting arbitrary incoming edges until SourceNode is reached.\n
  2. Tolerance is zero, and Graph did contain zero-length edges: in this case,\n SubGraph may contain (zero-length) cycles which one may want to exclude\n when constructing paths.\n
  3. Tolerance is nonzero: in this case, SubGraph may contain\n cycles (of maximum length Tolerance). Moreover, it may be\n possible to use the edges in SubGraph to construct cycle-free paths\n whose total length is greater than the shortest path length plus\n the tolerance. These may need to be excluded explicitly.\n
\n

")]). :- comment(all_shortest_paths / 4, hidden). :- comment(articulation_points / 2, [summary : "Finds the articulation points of the graph", amode : articulation_points(+, -), args : ["Graph" : "a graph structure", "Articulations" : "a list of integer node numbers"], see_also : [graph_is_bidirected / 1, critical_links / 2, biconnected_components / 3], desc : html("

\n Finds the articulation points of a graph, i.e. those nodes that,\n when deleted, would break the graph into two or more disconnected\n components. If there are no articulation points, the graph is\n called biconnected.\n

\n This operation is only defined for bidirected graphs.\n

")]). :- comment(biconnected_components / 3, [summary : "Finds the biconnected components of the graph", amode : biconnected_components(+, -, -), args : ["Graph" : "a graph structure", "Articulations" : "a list of integer node numbers", "BCC" : "list of lists of integer node numbers"], see_also : [graph_is_bidirected / 1, articulation_points / 2, strong_components / 2], desc : html("

\n Computes the biconnected components of a graph, i.e. maximal subsets of\n the graph's nodes whose nodes are mutually accessible via at least two\n distinct paths (in other words, subgraphs which have no articulation\n points).\n

\n Also compute a list of articulation points, i.e. those nodes that\n connect the biconnected components to each other.\n

\n This operation is only defined for bidirected graphs.\n

\n Note that by convention, isolated nodes and pairs of nodes connected\n by a single (bidirected) edge also form biconnected components.\n

")]). :- comment(connected_components / 2, [summary : "Computes the connected components of graph", amode : connected_components(+, -), args : ["Graph" : "a graph structure", "ConnectedComponents" : "a list of lists of node numbers"], see_also : [graph_is_bidirected / 1, articulation_points / 2], desc : html("

\n Computes the connected components of a (bidirected) graph. Each resulting\n connected component is represented as an (unsorted) list of nodes.\n

\n This operation is only defined on bidirected graphs.\n The runtime complexity is O(Nnodes + Nedges).\n

")]). :- comment(critical_links / 2, [summary : "Finds critical links in a bidirected graph", amode : critical_links(+, -), args : ["Graph" : "a graph structure", "Links" : "a list of edge pairs (output)"], fail_if : "Fails if the graph is not bidirected", see_also : [graph_is_bidirected / 1, articulation_points / 2], desc : html("

\n Finds all the critical links of a bidirected graph. We define an\n (bidirected) link as a pair of (oppositely directed) edges between\n two nodes. A critical link is one that, when removed, would make the\n graph more disconnected.\n

\n The result is returned as a list of links, where each link is a\n hyphenated pair of e/3 edge structures like e(I,J,Dij) - e(J,I,Dji).\n

")]). :- comment(graph_adjacent_edge / 3, [summary : "Succeeds if Edge is an edge adjacent to Node in Graph", amode : graph_adjacent_edge(+, +, ?), resat : yes, args : ["Graph" : "a graph structure", "Node" : "an integer node number", "Edge" : "an e/3 edge structure"], see_also : [graph_edge / 2, graph_get_adjacent_edges / 3], desc : html("

\n

")]). :- comment(graph_cycles / 2, [summary : "Computes a list of edges whose removal would make the graph acyclic", amode : graph_cycles(+, -), args : ["Graph" : "a graph structure", "BreakingEdges" : "a list of e/3 edge structures"], see_also : [graph_is_acyclic / 1, top_sort / 2], desc : html("

\n Computes a set of edges whose removal would make the graph acyclic.\n This set is not necessarily minimal, and it contains an arbitrary\n edge from every cycle in the graph.\n

\n If the list is empty, the graph is already acyclic.\n

")]). :- comment(graph_edge / 2, [summary : "Succeeds if Edge is an edge in graph", amode : graph_edge(+, ?), resat : yes, args : ["Graph" : "a graph structure", "Edge" : "an e/3 edge structure"], see_also : [graph_adjacent_edge / 3, graph_get_all_edges / 2], desc : html("

\n

")]). :- comment(graph_get_adjacent_edges / 3, [summary : "Returns a sorted list of all edges starting from SourceNode", amode : graph_get_adjacent_edges(+, +, -), args : ["Graph" : "a graph structure", "SourceNode" : "an integer node number", "EdgeList" : "a list of e/3 edge structures"], see_also : [graph_get_all_edges / 2, graph_get_incoming_edges / 3, graph_get_maxnode / 2], desc : html("

\n

")]). :- comment(graph_get_all_edges / 2, [summary : "Returns a sorted list of all edges in the graph", amode : graph_get_all_edges(+, -), args : ["Graph" : "a graph structure", "EdgeList" : "a list of e/3 edge structures"], see_also : [graph_get_adjacent_edges / 3, graph_get_incoming_edges / 3, graph_get_maxnode / 2], desc : html("

\n

")]). :- comment(graph_get_edge / 4, [summary : "Finds a graph edge given source and target node", amode : graph_get_edge(+, +, +, -), args : ["Graph" : "a graph structure", "Source" : "an integer node number", "Target" : "an integer node number", "Edge" : "an e/3 edge structure"], see_also : [graph_get_all_edges / 2, graph_get_adjacent_edges / 3, graph_edge / 2, graph_adjacent_edge / 3, graph_get_edges / 4], desc : html("

\n This operation is linear in the number of edges adjacent to Source.\n

")]). :- comment(graph_get_edges / 4, [summary : "Finds all edges between source node and target node", amode : graph_get_edges(+, +, +, -), args : ["Graph" : "a graph structure", "Source" : "an integer node number", "Target" : "an integer node number", "Edges" : "a list of e/3 edge structures"], see_also : [graph_get_all_edges / 2, graph_get_adjacent_edges / 3, graph_edge / 2, graph_adjacent_edge / 3, graph_get_edge / 4], desc : html("

\n This operation is linear in the number of edges adjacent to Source.\n

")]). :- comment(graph_get_incoming_edges / 3, [summary : "Returns a sorted list of all edges ending in TargetNode", amode : graph_get_incoming_edges(+, +, -), args : ["Graph" : "a graph structure", "TargetNode" : "an integer node number", "EdgeList" : "a list of e/3 edge structures"], see_also : [graph_get_all_edges / 2, graph_get_adjacent_edges / 3], desc : html("

\n Note on performance: By default, the graph structure only stores the\n outgoing (adjacent) edges of every node. The incoming edge lists are\n computed lazily when graph_get_incoming_edges/3 is called for the first\n time (but then they are built for all nodes at once). Therefore the\n first call to this predicate has O(NlogN) complexity, subsequent calls\n are only O(1). It may therefore make sense to do a dummy call to this\n predicate before starting time critical or nondeterministic computation.\n

")]). :- comment(graph_get_maxnode / 2, [summary : "Returns the highest node number in Graph", amode : graph_get_maxnode(+, -), args : ["Graph" : "a graph structure", "MaxNode" : "an integer node number"], see_also : [graph_get_all_edges / 2, graph_get_adjacent_edges / 3], desc : html("

\n Note that the smallest node number in a graph is always 1.\n

")]). :- comment(graph_get_nodenames / 2, [summary : "Returns the array of node names", amode : graph_get_nodenames(+, -), fail_if : "Fails if no node name information is available", args : ["Graph" : "a graph structure", "NodeNameArray" : "array of ground data, usually node names"], see_also : [graph_set_nodenames / 2], desc : html("

\n

")]). :- comment(graph_is_acyclic / 1, [summary : "Succeeds iff the given graph has no cycles", amode : graph_is_acyclic(+), args : ["Graph" : "a graph structure"], see_also : [top_sort / 2, graph_cycles / 2], fail_if : "No topological ordering exists, i.e. the graph is cyclic"]). :- comment(graph_is_bidirected / 1, [summary : "Tests whether a graph is bidirected", amode : graph_is_bidirected(+), args : ["Graph" : "a graph structure"], see_also : [make_undirected_graph / 2], desc : html("

\n A graph is bidirected if for every edge from S to T there is a\n corresponding edge from T to S. In case of loops (i.e. an edge\n from S to S) a second, different edge from S to S is required\n to satisfy the bidirectedness condition.\n

")]). :- comment(graph_node / 2, [summary : "Succeeds if Node is a node of the graph", amode : graph_node(+, ?), resat : yes, args : ["Graph" : "a graph structure", "Node" : "an integer node number"], see_also : [graph_get_maxnode / 2], desc : html("

\n

")]). :- comment(graph_reverse_edges / 2, [summary : "Makes a graph with reversed edges", amode : graph_reverse_edges(+, -), args : ["Graph" : "a graph structure", "RevGraph" : "a graph structure"], see_also : [make_graph / 3, make_graph_symbolic / 3], desc : html("

\n Creates a new graph RevGraph which is identical to Graph except\n that all edges are reversed.\n

")]). :- comment(graph_set_nodenames / 2, [summary : "Add node names to an existing graph", amode : graph_set_nodenames(+, ++), args : ["Graph" : "a graph structure", "NodeNameArray" : "array of ground data, usually node names"], see_also : [make_graph_symbolic / 3, graph_get_nodenames / 2], desc : html("

\n

")]). :- comment(graph_set_random_weights / 3, [summary : "Unifies all the graph's edge data fields with random numbers", amode : graph_set_random_weights(+, +, +), args : ["Graph" : "a graph structure", "Min" : "an integer or float", "Max" : "an integer or float"], see_also : [make_random_graph / 6, random / 1, frandom / 1], desc : html("

\n The input Graph is assumed to be a graph with uninstantiated edge\n data fields. These will be instantiated to random numbers between\n Min and Max, using random/1 if Min and Max are integers, or using\n frandom/1 if Min and Max are floats.\n

")]). :- comment(incremental_all_shortest_paths_as_edges / 6, [summary : "Incrementally computes all shortest paths from a single source to every reachable node given a list of modified edges", amode : incremental_all_shortest_paths_as_edges(+, +, +, +, -, -), args : ["Graph" : "a graph structure", "DistanceArg" : "which argument of EdgeData to use as distance (integer)", "SourceNode" : "source node number (integer)", "Modified" : "list of e/3 edge structures whose DistanceArg argument has been modified", "Lengths" : "array of numbers (minimum path lengths)", "Predecessors" : "array of lists of e/3 edge structures"], see_also : [possible_path / 7, shortest_paths / 4, single_pair_shortest_path / 5, all_short_paths_as_edges / 6, all_short_paths_as_graph / 6, incremental_all_shortest_paths_as_graph / 6, single_pair_short_path / 6, single_pair_all_short_paths_as_graph / 7], eg : "\n ?- sample_graph(G), incremental_all_shortest_paths_as_edges(G, 0, 1, M, L, E).\n L = [](0, 1, 2, 3, 2, 1, 1, _326, _327, 2, 3, 3, 3)\n E = []([], [e(1, 2, 1)], [e(7, 3, 1)], [e(5, 4, 1)],\n\t [e(7, 5, 1), e(6, 5, 1)], [e(1, 6, 1)], [e(1, 7, 1)],\n\t _342, _343, [e(7, 10, 1)], [e(10, 11, 1)], [e(10, 12, 1)],\n\t [e(10, 13, 1)])\n ", desc : html("

\n Incrementally computes all shortest paths from the single source\n node SourceNode to every sink node which is reachable from it\n given a list of modified edges. The result is returned in the form\n of the Predecessors array which contains all relevant edges.\n

\n DistanceArg refers to the graph's EdgeData information that was\n specified when the graph was constructed. If EdgeData is a simple\n number, then DistanceArg should be 0 and EdgeData will be taken\n as the length of the edge. If EdgeData is a compound data structure,\n DistanceArg should be a number between 1 and the arity of that\n structure and determines which argument of the EdgeData structure\n will be interpreted as the edge's length. Important: the distance\n information in EdgeData must be a positive number.\n

\n If DistanceArg is given as -1, then any EdgeData is ignored and\n the length of every edge is assumed to be equal to 1.\n

\n SourceNode is the common starting point for the computed paths.\n

\n Modified is the list of e/3 edge structures whose DistanceArg\n argument has been modified since the last computation for this\n SourceNode.\n

\n The result is returned in the form of two arrays, whose indices range\n over the possible sink nodes. The Lengths array indicates the length\n of a shortest path from SourceNode to the corresponding sink node.\n The Predecessors array is an array of edge lists, each list containing\n the alternative edges that are part of a shortest path from SourceNode\n to the corresponding sink node.\n

\n If there is no path from SourceNode to a sink node J, then both\n Lengths[J] and Predecessors[J] are uninstantiated. Otherwise,\n Lengths[J] contains the length of a shortest path from SourceNode to J.\n Predecessors[J] contains a list of alternative edges that lead from\n some predecessor node to J in a shortest path from SourceNode to J.\n Predecessors[SourceNode] is always the empty list [].\n

\n

Assembling Actual Paths

\n

\n To generate an actual path from the Predecessors array, start from the\n sink node J, select one of the alternative edges in Predecessors[J]\n to find a predecessor node, and continue this process until the SourceNode\n is reached. Depending on the parameters, the following 3 cases can occur:\n

    \n
  1. Graph did not contain zero-length edges: in this\n case, SubGraph is cycle-free and shortest paths can be found by simply\n selecting arbitrary incoming edges until SourceNode is reached.\n
  2. Graph did contain zero-length edges: in this case,\n SubGraph may contain (zero-length) cycles which one may want to exclude\n when constructing paths.\n
\n The possible_path/7 predicate implements this path construction and\n does the necesssary checks to exclude cycles.\n

")]). :- comment(incremental_all_shortest_paths_as_graph / 6, [summary : "Incrementally computes all shortest paths from a single source to every reachable node given a list of modified edges", amode : incremental_all_shortest_paths_as_graph(+, +, +, +, -, -), args : ["Graph" : "a graph structure", "DistanceArg" : "which argument of EdgeData to use as distance (integer)", "SourceNode" : "source node number (integer)", "Modified" : "list of e/3 edge structures whose DistanceArg argument has been modified", "Lengths" : "array of numbers (minimum path lengths)", "SubGraph" : "a graph structure"], see_also : [possible_path / 7, shortest_paths / 4, single_pair_shortest_path / 5, all_short_paths_as_edges / 6, all_short_paths_as_graph / 6, incremental_all_shortest_paths_as_edges / 6, single_pair_short_path / 6, single_pair_all_short_paths_as_graph / 7], eg : "\n ?- sample_graph(G), incremental_all_shortest_paths_as_graph(G, 0, 1, 0, L, E).\n G = graph(13, []([e(1, 6, 1), e(1, 2, 1), e(1, 7, 1)], [], ...)\n L = [](0, 1, 2, 3, 2, 1, 1, _326, _327, 2, 3, 3, 3)\n SG = graph(13, []([e(1, 7, 1), e(1, 6, 1), e(1, 2, 1)], [], ...)\n Yes (0.00s cpu)\n ", desc : html("

\n Incrementally computes all shortest paths from the single source\n node SourceNode to every sink node which is reachable from it. The\n result is returned in the form of a sub-graph of the input graph,\n which contains all relevant edges.\n

\n DistanceArg refers to the graph's EdgeData information that was\n specified when the graph was constructed. If EdgeData is a simple\n number, then DistanceArg should be 0 and EdgeData will be taken\n as the length of the edge. If EdgeData is a compound data structure,\n DistanceArg should be a number between 1 and the arity of that\n structure and determines which argument of the EdgeData structure\n will be interpreted as the edge's length. Important: the distance\n information in EdgeData must be a positive number.\n

\n If DistanceArg is given as -1, then any EdgeData is ignored and\n the length of every edge is assumed to be equal to 1.\n

\n SourceNode is the common starting point for the computed paths.\n

\n Modified is the list of e/3 edge structures whose DistanceArg\n argument has been modified since the last computation for this\n SourceNode.\n

\n The result is returned in the form of SubGraph, which is a\n sub-graph of the input Graph, containing the same nodes, but only\n those edges that are needed to construct the shortest paths for\n the given parameters. SubGraph does not inherit the nodename\n information from Graph, this can be set explicitly if required.\n

\n In addition, a Lengths array is returned, whose entries indicate\n the length of a shortest path from SourceNode to the corresponding\n sink node. If there is no path from SourceNode to a sink node J,\n then Lengths[J] is uninstantiated.\n

\n

Properties of the resulting SubGraph

\n

\n To generate an actual path from the resulting SubGraph, start from the\n sink node J, select one of its incoming edges (graph_get_incoming_edges/3)\n to find a predecessor node, and continue this process until the SourceNode\n is reached. Depending on the parameters, the following 3 cases can occur:\n

    \n
  1. Graph did not contain zero-length edges: in this\n case, SubGraph is cycle-free and shortest paths can be found by simply\n selecting arbitrary incoming edges until SourceNode is reached.\n
  2. Graph did contain zero-length edges: in this case,\n SubGraph may contain (zero-length) cycles which one may want to exclude\n when constructing paths.\n

    ")]). :- comment(incremental_single_pair_all_shortest_paths_as_graph / 7, [summary : "Computes all shortest paths from source to sink in form of a subgraph", amode : incremental_single_pair_all_shortest_paths_as_graph(+, +, +, +, +, -, -), args : ["Graph" : "a graph structure", "DistanceArg" : "which argument of EdgeData to use as distance (integer)", "SourceNode" : "source node number (integer)", "SinkNode" : "sink node number (integer)", "Modified" : "list of e/3 edge structures whose DistanceArg argument has been modified", "Length" : "a number (minimum path length)", "SubGraph" : "a graph structure"], see_also : [possible_path / 7, shortest_paths / 4, single_pair_shortest_path / 5, all_short_paths_as_edges / 6, all_short_paths_as_graph / 6, single_pair_short_path / 6, graph_get_incoming_edges / 3, graph_set_nodenames / 2], eg : "\n ?- sample_graph(G),\n incremental_single_pair_all_shortest_paths_as_graph(G, 0, 1, 5, M, L, E).\n G = graph(13, []([e(1, 6, 1), e(1, 2, 1), e(1, 7, 1)], [], ...)\n L = 2\n SG = graph(13, []([e(1, 6, 1), e(1, 7, 1)], [], ...)\n ", desc : html("

    \n Incrementally computes all shortest paths from source node\n SourceNode to sink node SinkNode. The result is returned in the\n form of a sub-graph of the input graph, which contains all\n relevant edges. If there is no path, the predicate fails.\n

    \n DistanceArg refers to the graph's EdgeData information that was\n specified when the graph was constructed. If EdgeData is a simple\n number, then DistanceArg should be 0 and EdgeData will be taken\n as the length of the edge. If EdgeData is a compound data structure,\n DistanceArg should be a number between 1 and the arity of that\n structure and determines which argument of the EdgeData structure\n will be interpreted as the edge's length. Important: the distance\n information in EdgeData must be a non-negative number.\n

    \n If DistanceArg is given as -1, then any EdgeData is ignored and\n the length of every edge is assumed to be equal to 1.\n

    \n Modified is the list of e/3 edge structures whose DistanceArg\n argument has been modified since the last computation for this\n SourceNode.\n

    \n The result is returned in the form of SubGraph, which is a\n sub-graph of the input Graph, containing the same nodes, but only\n those edges that are needed to construct the shortest paths for\n the given parameters. SubGraph does not inherit the nodename\n information from Graph, this can be set explicitly if required.\n

    \n In addition, the Length of the shortest path from source to sink\n is returned.\n

    \n

    Properties of the resulting SubGraph

    \n

    \n To generate an actual path from the resulting SubGraph, start from the\n sink node J, select one of its incoming edges (graph_get_incoming_edges/3)\n to find a predecessor node, and continue this process until the SourceNode\n is reached. Depending on the input graph, the following 2 cases can occur:\n

      \n
    1. Graph did not contain zero-length edges: in this case,\n SubGraph is cycle-free and shortest paths can be found by simply \n selecting arbitrary incoming edges until SourceNode is reached.\n
    2. Graph did contain zero-length edges: in this case, SubGraph\n may contain (zero-length) cycles which one may want to exclude \n when constructing paths.\n
    \n

    ")]). :- comment(incremental_single_pair_shortest_path / 6, [summary : "Computes short paths from a source to a sink node", amode : incremental_single_pair_shortest_path(+, +, +, +, +, -), args : ["Graph" : "a graph structure", "DistanceArg" : "which argument of EdgeData to use as distance: integer", "SourceNode" : "source node number (integer)", "SinkNode" : "sink node number (integer)", "Modified" : "list of e/3 edge structures whose DistanceArg argument has been modified", "Path" : "Length-EdgeList structure"], see_also : [shortest_paths / 4, single_pair_shortest_path / 5, all_short_paths_as_edges / 6, all_short_paths_as_graph / 6, incremental_all_shortest_paths_as_edges / 6, incremental_all_shortest_paths_as_graph / 6, single_pair_short_path / 6, single_pair_all_short_paths_as_graph / 7, possible_path / 7], fail_if : "There is no path from SourceNode to SinkNode", resat : yes, eg : "\n ?- sample_graph(G), incremental_single_pair_shortest_path(G, 0, 1, M, P).\n P = 2 - [e(2, 3, 1), e(1, 2, 1)]\n ", desc : html("

    \n Incrementally computes shortest paths from SourceNode to SinkNode.\n Alternative paths are generated on backtracking. Fails if there is\n no path at all.\n

    \n DistanceArg refers to the graph's EdgeData information that was\n specified when the graph was constructed. If EdgeData is a simple\n number, then DistanceArg should be 0 and EdgeData will be taken\n as the length of the edge. If EdgeData is a compound data structure,\n DistanceArg should be a number between 1 and the arity of that\n structure and determines which argument of the EdgeData structure\n will be interpreted as the edge's length. Important: the distance\n information in EdgeData must be a positive number.\n

    \n If DistanceArg is given as -1, then any EdgeData is ignored and\n the length of every edge is assumed to be equal to 1.\n

    \n Modified is the list of e/3 edge structures whose DistanceArg\n argument has been modified since the last computation for this\n SourceNode.\n

    \n All paths returned will have the same length and will be shortest\n paths from SourceNode to SinkNode. Note that the solutions are not\n generated in any specific order.\n

    \n A resulting path is returned as a Length-EdgeList structure where\n Length is the length of the path and EdgeList is the path in\n reverse order, i.e. starting with the edge reaching SinkNode and\n ending with the edge starting from SourceNode.\n

    ")]). :- comment(is_sub_graph / 2, [summary : "Succeeds iff SubGraph is a subgraph of SuperGraph", amode : is_sub_graph(+, +), args : ["SubGraph" : "a graph structure", "SuperGraph" : "a graph structure"], see_also : [make_sub_graph / 3], fail_if : "SubGraph is not a subgraph of SuperGraph", desc : html("\n Tests whether SubGraph is a (non-strict) subgraph of SuperGraph.\n This is the case when the nodes and edges in SubGraph are a subset\n of the nodes and edges of SuperGraph. Note that nodes are considered\n identical when they have the same node numbers (rather than the same\n node names - node name information is ignored by this predicate.).\n ")]). :- comment(make_graph / 3, [summary : "Creates a graph with minimal overhead", amode : make_graph(+, ++, -), args : ["NNodes" : "the number of nodes: integer >= 0", "EdgeList" : "a (possibly empty) list of e/3 structures in no particular order", "Graph" : "will be bound to a graph structure"], fail_if : "Edges contain nonexisting node numbers", exceptions : [6 : "NNodes is negative", 4 : "NNodes or EdgeList are uninstantiated", 5 : "NNodes is not integral"], see_also : [make_graph_symbolic / 3, graph_set_nodenames / 2, library(graphviz), compare / 3], eg : "\n % the 13-node undirected graph from Sedgewick:Algorithms\n make_graph( 13,\n\t[ e(1,6,1),e(1,2,1),e(1,7,1),e(3,1,1),e(4,6,1),e(5,4,1),\n\t e(6,5,1),e(7,5,1),e(7,10,1),e(7,3,1),e(8,7,1),e(8,9,1),e(9,8,1),\n\t e(10,11,1),e(10,12,1),e(10,13,1),e(12,7,1),e(12,13,1),e(13,12,1) ],\n Graph).", desc : html("

    \n This predicate creates a graph data structure according to the given\n information. A graph consists of nodes that are numbered from 1 to\n NNodes and directed edges between the nodes. An edge is represented\n by the data structure\n

    \n\te(Source, Target, EdgeData)\n
    \n where Source and Target are integers indicating the start and end\n point of the edge, and EdgeData is an arbitrary data structure\n holding additional information about the edge, e.g. capacity,\n distance, weight, name etc. The EdgeData field should have the\n same structure for all edges in the graph. If there is no\n information attached to edges, the field should be set to 1\n for edges between different nodes and to 0 otherwise.\n Several library predicates inspect the EdgeData field or an argument\n of the EdgeData field, e.g. the shortest path predicate can\n use any numeric component of EdgeData as the distance criterion.\n Caution: the distance arguments will be compared using general term\n comparison (see compare/3) and should therefore have the same\n type in all edges (e.g. all integer or all float).\n

    ")]). :- comment(make_graph_symbolic / 3, [summary : "Creates a graph using node names", amode : make_graph_symbolic(+, ++, -), args : ["NodeNameArray" : "array of ground data, usually node names", "SymbolicEdgeList" : "(possibly empty) list of edge/3 structures in no particular order", "Graph" : "will be bound to a graph structure"], see_also : [make_graph / 3, library(graphviz)], eg : "\n % the 13-node undirected graph from Sedgewick:Algorithms\n make_graph_symbolic(\n\t[](a,b,c,d,e,f,g,h,i,j,k,l,m),\n\t[ edge(a,f,1),edge(a,b,1),edge(a,g,1),edge(c,a,1),edge(d,f,1),edge(e,d,1),\n\t edge(f,e,1),edge(g,e,1),edge(g,j,1),edge(g,c,1),edge(h,g,1),edge(h,i,1),edge(i,h,1),\n\t edge(j,k,1),edge(j,l,1),edge(j,m,1),edge(l,g,1),edge(l,m,1),edge(m,l,1) ],\n\tGraph).\n ", desc : html("

    \n This predicate is similar to make_graph/3 in that it creates a\n graph data structure according to the given information.\n If the nodes have names, then make_graph_symbolic/3 allows to\n specify the graph in a more readable way by using the node names\n rather than node numbers in the edge specifications.\n The node names are given as the array NodeNameArray, and the\n symbolic edges are written in the form\n

    \n\tedge(SourceName, TargetName, EdgeData)\n
    \n where SourceName and TargetName should match an entry (usually the\n node name) in NodeNameArray. Note the use of the functor edge/3 for\n the symbolic edge representation as opposed to e/3 for the internal\n edge representation.\n

    ")]). :- comment(make_random_graph / 6, [summary : "Creates a random graph with the given properties", amode : make_random_graph(+, +, +, +, +, -), args : ["NNodes" : "integer", "NEdges" : "integer", "AntiParallelFree" : "one of the atoms true or false", "LoopFree" : "one of the atoms true or false", "ParallelFree" : "one of the atoms true or false", "Graph" : "will be bound to a graph structure"], exceptions : [6 : "NEdges is too large given the chosen options and NNodes"], see_also : [graph_set_nodenames / 2, graph_get_all_edges / 2, graph_set_random_weights / 3, graph_get_adjacent_edges / 3, library(graphviz)], desc : html("

    \n Creates a random graph with NNodes nodes and NEdges edges.\n The other 3 options mean:\n

    \n
    AntiParallelFree
    \n
    if true, the graph will have no anti-parallel edges, i.e. if\n there is an edge from S to T, there won't be one from T to S
    \n
    LoopFree
    \n
    if true, the graph will have no self loops, i.e. no edges\n that begin and end in the same node.
    \n
    ParallelFree
    \n
    if true, the graph will have no parallel edges, i.e. there\n will be at most one edge from S to T.
    \n
    \n The generated graph has no node name information and no edge data.\n Node names can be added using graph_set_nodenames/2. Edge data\n (e.g. random weights) can be added by retrieving the edges using\n graph_get_all_edges/2 or graph_get_adjacent_edges/3 and unifying\n the variable EdgeData field with the required information.\n

    ")]). :- comment(make_sub_graph / 3, [summary : "Creates a subgraph (projection on nodes) of a given graph", amode : make_sub_graph(+, ++, -), args : ["Graph" : "a graph structure", "Nodes" : "a list of node numbers", "SubGraph" : "will be bound to a graph structure"], see_also : [is_sub_graph / 2], desc : html("

    \n Creates a sub-graph SubGraph of the original graph Graph. SubGraph has\n the same set of nodes as Graph, but only those edges that begin and end\n in the specified set of nodes Nodes.\n

    ")]). :- comment(make_undirected_graph / 2, [summary : "Creates an undirected from a directed graph", amode : make_undirected_graph(+, -), args : ["DirectedGraph" : "a graph structure", "UndirectedGraph" : "will be bound to a graph structure"], see_also : [graph_is_bidirected / 1], desc : html("

    \n Creates an undirected graph from a directed graph by adding reverse\n edges for every existing edge. Moreover, all loops (edges from S to S)\n are removed from the undirected graph.\n

    ")]). :- comment(maximum_matching_hopcroft_karp / 4, [summary : "Compute the maximum matching in a bipartite graph using Hopcroft and Karp's algorithm", amode : maximum_matching_hopcroft_karp(+, ++, ++, -), args : ["G" : "A directed bipartite graph, with all edges starting and ending in 'A' or 'B'", "A" : "List of nodes in one half of the graph", "B" : "List of nodes in the other half of the graph", "MaximalM" : "List of edges constituting the maximum matching"], desc : html("

    \n\n Computes the maximum matching in the given bipartite graph. A\n matching in a bipartite graph, is a set of edges from the\n graph such that no two edges are incident to the same node. A\n maximum matching is a matching with the most edges possible.\n The may be more than one maximum matching, this predicate\n returns only one.\n\n

    \n\n The implementation uses Hopcroft and Karp's algorithm which\n has a complexity of O(Nedges*SQRT(Nnodes in A)).\n

    "), fail_if : "Graph is not bipartite", resat : no, eg : "", see_also : [], index : ["matching", "bipartite matching"]]). :- comment(minimum_spanning_forest / 5, [summary : "Computes a minimum spanning forest, its size and weight", amode : minimum_spanning_forest(+, +, -, -, -), args : ["Graph" : "a graph structure", "DistanceArg" : "which argument of EdgeData to use as distance: integer", "Forest" : "a list of e/3 edge structures", "ForestSize" : "the number of edges in the Forest list", "ForestWeight" : "sum of the forest's edge weights: number"], index : ["spanning forest"], see_also : [minimum_spanning_tree / 4], eg : "\n ?- sample_graph(G), minimum_spanning_forest(G, 0, T, S, W).\n T = [e(2, 10, 1), e(4, 8, 1), e(9, 2, 1), e(7, 3, 2), ...]\n S = 8\n W = 16\n ", desc : html("

    \n Computes a minimum spanning forest for the given graph. A minimum\n spanning forest is a smallest subset of the graph's edges that still\n connects all the graph's connected components. Such a forest is not\n unique, but all minimum spanning forests will have the same cost.\n As opposed to a minimum spanning tree, a forest exists also if the\n original graph is not connnected. The forest will have the same\n number of connected components as the original graph.\n

    \n The computed forest is returned in Forest, which is simply a list of\n the edges that form the forest. The ForestSize is the number of\n edges that constitute the forest. The ForestWeight is the total\n length of the forest's edges, according to DistanceArg.\n

    \n DistanceArg refers to the graph's EdgeData information that was\n specified when the graph was constructed. If EdgeData is a simple\n number, then DistanceArg should be 0 and EdgeData will be taken\n as the length of the edge. If EdgeData is a compound data structure,\n DistanceArg should be a number between 1 and the arity of that\n structure and determines which argument of the EdgeData structure\n will be interpreted as the edge's length. Important: the distance\n information in EdgeData must be a non-negative number, and the\n numeric type (integer, float, etc) must be the same in all edges.\n

    \n If DistanceArg is given as -1, then any EdgeData is ignored and\n the length of every edge is assumed to be equal to 1.\n

    \n The direction of the graph's edges is ignored by this predicate.\n

    \n The implementation uses Kruskal's algorithm which has a complexity\n of O(Nedges*log(Nedges)).\n

    ")]). :- comment(minimum_spanning_tree / 4, [summary : "Computes a minimum spanning tree and its weight", amode : minimum_spanning_tree(+, +, -, -), args : ["Graph" : "a graph structure", "DistanceArg" : "which argument of EdgeData to use as distance: integer", "Tree" : "a list of e/3 edge structures", "TreeWeight" : "sum of the tree's edge weights: number"], index : ["spanning tree"], fail_if : "No spanning tree exists, i.e. the graph is not connected.", see_also : [minimum_spanning_forest / 5], eg : "\n ?- sample_graph(G), minimum_spanning_tree(G, 0, T, W).\n T = [e(2, 10, 1), e(4, 8, 1), e(9, 2, 1), e(7, 3, 2), ...]\n W = 16\n ", desc : html("

    \n Computes a minimum spanning tree for the given graph. A minimum\n spanning tree is a smallest subset of the graph's edges that still\n connects all the graph's nodes. Such a tree is not unique and of\n course exists only if the original graph is itself connected.\n However, all minimum spanning trees will have the same cost.\n

    \n The computed tree is returned in Tree, which is simply a list of\n the edges that form the tree. The TreeWeight is the total length\n of the tree's edges, according to DistanceArg.\n

    \n DistanceArg refers to the graph's EdgeData information that was\n specified when the graph was constructed. If EdgeData is a simple\n number, then DistanceArg should be 0 and EdgeData will be taken\n as the length of the edge. If EdgeData is a compound data structure,\n DistanceArg should be a number between 1 and the arity of that\n structure and determines which argument of the EdgeData structure\n will be interpreted as the edge's length. Important: the distance\n information in EdgeData must be a non-negative number, and the\n numeric type (integer, float, etc) must be the same in all edges.\n

    \n If DistanceArg is given as -1, then any EdgeData is ignored and\n the length of every edge is assumed to be equal to 1.\n

    \n The direction of the graph's edges is ignored by this predicate.\n

    \n The implementation uses Kruskal's algorithm which has a complexity\n of O(Nedges*log(Nedges)).\n

    ")]). :- comment(node_to_nodename / 3, [summary : "Retrieves the name of a node", amode : node_to_nodename(+, +, -), fail_if : "Fails if no node name information is available", args : ["Graph" : "a graph structure", "Node" : "an integer node number", "NodeName" : "ground data, usually node name"], see_also : [nodes_to_nodenames / 3, nodename_to_node / 3, nodenames_to_nodes / 3], desc : html("

    \n

    ")]). :- comment(nodename_to_node / 3, [summary : "Retrieves the node number given a node name", amode : nodename_to_node(+, +, -), fail_if : "Fails if no node name information is available", args : ["Graph" : "a graph structure", "NodeName" : "ground data, usually node name", "Node" : "an integer node number"], see_also : [node_to_nodename / 3, nodes_to_nodenames / 3, nodenames_to_nodes / 3], desc : html("

    \n

    ")]). :- comment(nodenames_to_nodes / 3, [summary : "Returns the names corresponding to a list of nodes", amode : nodenames_to_nodes(+, +, -), fail_if : "Fails if no node name information is available", args : ["Graph" : "a graph structure", "NodeNames" : "a list of ground data, usually node names", "Nodes" : "a list of integer node numbers"], see_also : [node_to_nodename / 3, nodename_to_node / 3, nodes_to_nodenames / 3], desc : html("

    \n

    ")]). :- comment(nodes_to_nodenames / 3, [summary : "Returns the names corresponding to a list of nodes", amode : nodes_to_nodenames(+, +, -), fail_if : "Fails if no node name information is available", args : ["Graph" : "a graph structure", "Nodes" : "a list of integer node numbers", "NodeNames" : "a list of ground data, usually node names"], see_also : [node_to_nodename / 3, nodename_to_node / 3, nodenames_to_nodes / 3], desc : html("

    \n

    ")]). :- comment(possible_path / 6, [summary : "Computes an actual path from a predecessors array", amode : possible_path(+, +, +, +, +, -), args : ["SourceNode" : "source node number", "SinkNode" : "sink node number", "Tolerance" : "tolerable deviation from minimal length (non-negative number)", "Lengths" : "array of numbers", "Predecessors" : "array of edge lists", "Path" : "Length-EdgeList structure"], see_also : [possible_path / 7], desc : html("

    \n This predicate is deprecated, it is equivalent to possible_path/7 with\n a DistanceArg of 0.\n

    ")]). :- comment(possible_path / 7, [summary : "Computes an actual path from a predecessors array", amode : possible_path(+, +, +, +, +, +, -), args : ["DistanceArg" : "which argument of EdgeData to use as distance (integer)", "SourceNode" : "source node number", "SinkNode" : "sink node number", "Tolerance" : "tolerable deviation from minimal length (non-negative number)", "Lengths" : "array of numbers", "Predecessors" : "array of edge lists", "Path" : "Length-EdgeList structure"], see_also : [all_short_paths_as_edges / 6], fail_if : "There is no path to SinkNode", resat : yes, eg : "\n single_pair_shortest_path(Graph, Source, Sink, Path) :-\n \tall_short_paths_as_edges(Graph, 0, Source, 0, Lengths, Preds),\n \tpossible_path(0, Source, Sink, 0, Lengths, Preds, Path).\n ", desc : html("

    \n This predicate complements the all_short_paths_as_edges/6 predicate.\n The intended usage is that all_short_paths_as_edges/6 is used to\n precompute shortest path information from a single source node\n to all possible sink nodes, and possible_path/7 uses this\n information to enumerate actual paths to a specific sink node.\n If paths from one source to several sinks are needed, it is more\n efficient to use one call to all_short_paths_as_edges/6 and several\n calls to possible_path/7, than to use several calls to\n single_pair_all_short_paths/7.\n

    \n Note that the Lengths and Predecessors arrays must have been computed\n with the same settings for DistanceArg, SourceNode and Tolerance that are\n given to possible_path/7, otherwise errors or missing paths will occur.\n

    ")]). :- comment(proper_graph / 1, [summary : "Tests the integrity of the given graph data structure", amode : proper_graph(+), args : ["Graph" : "a graph structure"], see_also : [], desc : html("

    \n

    ")]). :- comment(shortest_paths / 4, [summary : "Computes one shortest path from a single source to every reachable node", amode : shortest_paths(+, +, +, -), args : ["Graph" : "a graph structure", "DistanceArg" : "which argument of EdgeData to use as distance: integer", "SourceNode" : "source node number (integer)", "Paths" : "array of Length-EdgeList structures"], see_also : [single_pair_shortest_path / 5, all_short_paths_as_edges / 6, all_short_paths_as_graph / 6, single_pair_short_path / 6, single_pair_all_short_paths_as_graph / 7, possible_path / 7], resat : no, eg : "\n ?- sample_graph(G), shortest_paths(G, 0, 1, P).\n P = [](2 - [e(2, 1, 1), e(1, 2, 1)], 1 - [e(1, 2, 1)], ...)\n ", desc : html("

    \n Computes one shortest path from the single source node SourceNode\n to every node which is reachable from it. In case of multiple\n shortest paths with the same length, an arbitrary one is returned.\n

    \n DistanceArg refers to the graph's EdgeData information that was\n specified when the graph was constructed. If EdgeData is a simple\n number, then DistanceArg should be 0 and EdgeData will be taken\n as the length of the edge. If EdgeData is a compound data structure,\n DistanceArg should be a number between 1 and the arity of that\n structure and determines which argument of the EdgeData structure\n will be interpreted as the edge's length. Important: the distance\n information in EdgeData must be a non-negative number, and the\n numeric type (integer, float, etc) must be the same in all edges.\n

    \n If DistanceArg is given as -1, then any EdgeData is ignored and\n the length of every edge is assumed to be equal to 1.\n

    \n SourceNode is the common starting point for the computed paths.\n

    \n The results are returned as an array ranging over all node numbers.\n For unreachable nodes the array element is uninstantiated.\n For reachable nodes, the element contains a Length-EdgeList structure\n where Length is the length of the shortest path and EdgeList is that\n path (or one of them) in reverse order, i.e. starting with the edge\n reaching the target and ending with the edge starting from SourceNode.\n

    ")]). :- comment(shortest_paths_bellman_ford / 4, [summary : "Computes one shortest path from a single source to every reachable node (allowing negative distances)", amode : shortest_paths_bellman_ford(+, +, +, -), args : ["Graph" : "a graph structure", "DistanceArg" : "which argument of EdgeData to use as distance: integer", "SourceNode" : "source node number", "Paths" : "array of Length-EdgeList structures"], see_also : [single_pair_shortest_path_bellman_ford / 5, shortest_paths / 4], eg : "\n ?- sample_graph(G), shortest_paths_bellman_ford(G, 0, 1, P).\n P = [](2 - [e(2, 1, 1), e(1, 2, 1)], 1 - [e(1, 2, 1)], ...)\n ", desc : html("

    \n Computes one shortest path from the single source node SourceNode\n to every node which is reachable from it. In case of multiple\n shortest paths with the same length, an arbitrary one is returned.\n

    \n DistanceArg refers to the graph's EdgeData information that was\n specified when the graph was constructed. If EdgeData is a simple\n number, then DistanceArg should be 0 and EdgeData will be taken\n as the length of the edge. If EdgeData is a compound data structure,\n DistanceArg should be a number between 1 and the arity of that\n structure and determines which argument of the EdgeData structure\n will be interpreted as the edge's length. As opposed to the other\n shortest path algorithms, the Bellman-Ford algorithm can handle\n negative edge lengths, however, the implementation has currently\n no check for negative cycles and will not terminate in that case.\n

    \n If DistanceArg is given as -1, then any EdgeData is ignored and\n the length of every edge is assumed to be equal to 1.\n

    \n SourceNode is the common starting point for the computed paths.\n

    \n The results are returned as an array ranging over all node numbers.\n For unreachable nodes the array element is uninstantiated.\n For reachable nodes, the element contains a Length-EdgeList structure\n where Length is the length of the shortest path and EdgeList is that\n path (or one of them) in reverse order, i.e. starting with the edge\n reaching the target and ending with the edge starting from SourceNode.\n

    ")]). :- comment(single_pair_all_short_paths_as_graph / 7, [summary : "Computes all shortest paths from source to sink in form of a subgraph", amode : single_pair_all_short_paths_as_graph(+, +, +, +, +, -, -), args : ["Graph" : "a graph structure", "DistanceArg" : "which argument of EdgeData to use as distance (integer)", "SourceNode" : "source node number (integer)", "SinkNode" : "sink node number (integer)", "Tolerance" : "tolerable deviation from minimal length (non-negative number)", "Length" : "a number (minimum path length)", "SubGraph" : "a graph structure"], see_also : [possible_path / 7, shortest_paths / 4, single_pair_shortest_path / 5, all_short_paths_as_edges / 6, all_short_paths_as_graph / 6, single_pair_short_path / 6, graph_get_incoming_edges / 3, graph_set_nodenames / 2], eg : "\n ?- sample_graph(G),\n single_pair_all_short_paths_as_graph(G, 0, 1, 5, 0, L, E).\n G = graph(13, []([e(1, 6, 1), e(1, 2, 1), e(1, 7, 1)], [], ...)\n L = 2\n SG = graph(13, []([e(1, 6, 1), e(1, 7, 1)], [], ...)\n ", desc : html("

    \n Computes all shortest paths from source node SourceNode to sink\n node SinkNode. The result is returned in the form of a sub-graph\n of the input graph, which contains all relevant edges.\n If there is no path, the predicate fails.\n

    \n DistanceArg refers to the graph's EdgeData information that was\n specified when the graph was constructed. If EdgeData is a simple\n number, then DistanceArg should be 0 and EdgeData will be taken\n as the length of the edge. If EdgeData is a compound data structure,\n DistanceArg should be a number between 1 and the arity of that\n structure and determines which argument of the EdgeData structure\n will be interpreted as the edge's length. Important: the distance\n information in EdgeData must be a non-negative number.\n

    \n If DistanceArg is given as -1, then any EdgeData is ignored and\n the length of every edge is assumed to be equal to 1.\n

    \n Tolerance should be zero in order to find only the shortest paths. \n If Tolerance is greater than zero, then all paths that are within\n this tolerance of the shortest path length will be found.\n

    \n The result is returned in the form of SubGraph, which is a\n sub-graph of the input Graph, containing the same nodes, but only\n those edges that are needed to construct the shortest paths for\n the given parameters. SubGraph does not inherit the nodename\n information from Graph, this can be set explicitly if required.\n

    \n In addition, the Length of the shortest path from source to sink\n is returned.\n

    \n

    Properties of the resulting SubGraph

    \n

    \n To generate an actual path from the resulting SubGraph, start from the\n sink node J, select one of its incoming edges (graph_get_incoming_edges/3)\n to find a predecessor node, and continue this process until the SourceNode\n is reached. Depending on the parameters, the following 3 cases can occur:\n

      \n
    1. Tolerance is zero, and Graph did not contain zero-length edges: in this\n case, SubGraph is cycle-free and shortest paths can be found by simply\n selecting arbitrary incoming edges until SourceNode is reached.\n
    2. Tolerance is zero, and Graph did contain zero-length edges: in this case,\n SubGraph may contain (zero-length) cycles which one may want to exclude\n when constructing paths.\n
    3. Tolerance is nonzero: in this case, SubGraph may contain\n cycles (of maximum length Tolerance). Moreover, it may be\n possible to use the edges in SubGraph to construct cycle-free paths\n whose total length is greater than the shortest path length plus\n the tolerance. These may need to be excluded explicitly.\n
    \n

    ")]). :- comment(single_pair_all_shortest_paths / 5, hidden). :- comment(single_pair_short_path / 6, [summary : "Computes short paths from a source to a sink node", amode : single_pair_short_path(+, +, +, +, +, -), args : ["Graph" : "a graph structure", "DistanceArg" : "which argument of EdgeData to use as distance: integer", "SourceNode" : "source node number (integer)", "SinkNode" : "sink node number (integer)", "Tolerance" : "tolerable deviation from minimal length (non-negative number)", "Path" : "Length-EdgeList structure"], see_also : [shortest_paths / 4, single_pair_shortest_path / 5, all_short_paths_as_edges / 6, all_short_paths_as_graph / 6, single_pair_all_short_paths_as_graph / 7, possible_path / 7], fail_if : "There is no path from SourceNode to SinkNode", resat : yes, eg : "\n ?- sample_graph(G), single_pair_short_path(G, 0, 1, 3, P).\n P = 2 - [e(2, 3, 1), e(1, 2, 1)]\n ", desc : html("

    \n Computes shortest (or sufficiently short) paths from SourceNode to\n SinkNode. Alternative paths are generated on backtracking.\n Fails if there is no path at all.\n

    \n DistanceArg refers to the graph's EdgeData information that was\n specified when the graph was constructed. If EdgeData is a simple\n number, then DistanceArg should be 0 and EdgeData will be taken\n as the length of the edge. If EdgeData is a compound data structure,\n DistanceArg should be a number between 1 and the arity of that\n structure and determines which argument of the EdgeData structure\n will be interpreted as the edge's length. Important: the distance\n information in EdgeData must be a non-negative number.\n

    \n If DistanceArg is given as -1, then any EdgeData is ignored and\n the length of every edge is assumed to be equal to 1.\n

    \n If Tolerance is given as zero, all paths returned will have the same\n length and will be shortest paths from SourceNode to SinkNode.\n If Tolerance is nonzero, additional paths will be returned with\n lengths up to the length of the shortest path plus the tolerance.\n Note that the solutions are not generated in any specific order.\n

    \n A resulting path is returned as a Length-EdgeList structure where\n Length is the length of the path and EdgeList is the path in\n reverse order, i.e. starting with the edge reaching SinkNode and\n ending with the edge starting from SourceNode.\n

    ")]). :- comment(single_pair_shortest_path / 5, [summary : "Computes one shortest path from a source to a sink node", amode : single_pair_shortest_path(+, +, +, +, -), args : ["Graph" : "a graph structure", "DistanceArg" : "which argument of EdgeData to use as distance: integer", "SourceNode" : "source node number (integer)", "SinkNode" : "sink node number (integer)", "Path" : "Length-EdgeList structure"], see_also : [shortest_paths / 4, all_short_paths_as_edges / 6, all_short_paths_as_graph / 6, single_pair_short_path / 6, single_pair_all_short_paths_as_graph / 7, possible_path / 7], fail_if : "There is no path from SourceNode to SinkNode", resat : no, eg : "\n ?- sample_graph(G), single_pair_shortest_path(G, 0, 1, 3, P).\n P = 2 - [e(2, 3, 1), e(1, 2, 1)]\n ", desc : html("

    \n Computes one shortest path from SourceNode to SinkNode.\n Fails if there is no path at all. In case of multiple\n shortest paths with the same length, an arbitrary one is returned.\n

    \n DistanceArg refers to the graph's EdgeData information that was\n specified when the graph was constructed. If EdgeData is a simple\n number, then DistanceArg should be 0 and EdgeData will be taken\n as the length of the edge. If EdgeData is a compound data structure,\n DistanceArg should be a number between 1 and the arity of that\n structure and determines which argument of the EdgeData structure\n will be interpreted as the edge's length. Important: the distance\n information in EdgeData must be a non-negative number, and the\n numeric type (integer, float, etc) must be the same in all edges.\n

    \n If DistanceArg is given as -1, then any EdgeData is ignored and\n the length of every edge is assumed to be equal to 1.\n

    \n The shortest path is returned as a Length-EdgeList structure\n where Length is the length of the shortest path and EdgeList is that\n path (or one of them) in reverse order, i.e. starting with the edge\n reaching SinkNode and ending with the edge starting from SourceNode.\n

    ")]). :- comment(single_pair_shortest_path_bellman_ford / 5, [summary : "Computes one shortest path from a source to a sink node (allowing negative distances)", amode : single_pair_shortest_path_bellman_ford(+, +, +, +, -), args : ["Graph" : "a graph structure", "DistanceArg" : "which argument of EdgeData to use as distance: integer", "SourceNode" : "source node number", "SinkNode" : "sink node number", "Path" : "Length-EdgeList structure"], see_also : [shortest_paths_bellman_ford / 4, single_pair_shortest_path / 5], fail_if : "There is no path from SourceNode to SinkNode", eg : "\n ?- sample_graph(G), single_pair_shortest_path_bellman_ford(G, 0, 1, 3, P).\n P = 2 - [e(2, 3, 1), e(1, 2, 1)]\n ", desc : html("

    \n Computes one shortest path from SourceNode to SinkNode.\n Fails if there is no path at all. In case of multiple\n shortest paths with the same length, an arbitrary one is returned.\n

    \n DistanceArg refers to the graph's EdgeData information that was\n specified when the graph was constructed. If EdgeData is a simple\n number, then DistanceArg should be 0 and EdgeData will be taken\n as the length of the edge. If EdgeData is a compound data structure,\n DistanceArg should be a number between 1 and the arity of that\n structure and determines which argument of the EdgeData structure\n will be interpreted as the edge's length. As opposed to the other\n shortest path algorithms, the Bellman-Ford algorithm can handle\n negative edge lengths, however, the implementation has currently\n no check for negative cycles and will not terminate in that case.\n

    \n If DistanceArg is given as -1, then any EdgeData is ignored and\n the length of every edge is assumed to be equal to 1.\n

    \n The shortest path is returned as a Length-EdgeList structure\n where Length is the length of the shortest path and EdgeList is that\n path (or one of them) in reverse order, i.e. starting with the edge\n reaching SinkNode and ending with the edge starting from SourceNode.\n

    ")]). :- comment(strong_components / 2, [summary : "Computes the strongly connected components of a graph", amode : strong_components(+, -), args : ["Graph" : "a graph structure", "StrongComponents" : "list of lists of integer node numbers"], see_also : [], desc : html("

    \n Computes the strongly connected components, i.e. maximal subsets\n of the graph's nodes in which all nodes are mutually accessible.\n The implementation essentially uses Tarjan's algorithm with a\n complexity of O(Nnodes + Nedges).\n

    ")]). :- comment(top_sort / 2, [summary : "Finds a topological ordering of the graph if one exists", amode : top_sort(+, -), args : ["Graph" : "a graph structure", "Sorted" : "a list of integer node numbers"], see_also : [graph_is_acyclic / 1, graph_cycles / 2], fail_if : "No topological ordering exists, i.e. the graph is cyclic", desc : html("

    \n Finds a topological ordering of the graph, i.e. an ordering of the\n nodes such that all edges go from earlier to later nodes.\n Such an ordering exists if and only if the graph is acyclic.\n If the graph is cyclic, the predicate fails.\n

    \n In general, the ordering is not unique, an arbitrary one is computed.\n The complexity is O(Nnodes + Nedges).\n

    ")]).